package com.leetCode.problem;

import javax.print.attribute.standard.NumberUp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-22 16:29:35
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-22     张李鑫                     1.0         1.0 Version
 */
public class Problem45 {

    /**
     * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
     * <p>
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * <p>
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * <p>
     * 假设你总是可以到达数组的最后一个位置。
     */
    public static int jump(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        //当前步数
        int step = 1;
        int right = nums[0];
        int nextRight = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > right) {
                step++;
                right = nextRight;
                if (right >= nums.length - 1) {
                    return step;
                }
            }
            nextRight = Math.max(i + nums[i], nextRight);
        }
        return step;
    }


    /**
     * 给定一个数组 给一个开始位置 给一个结束位置
     * 要几步能到end
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int jump3(int[] arr, int start, int end) {
        return 0;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2};
        System.out.println(jump(arr));
    }
}
